/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM37 二叉搜索树的最近公共祖先
 * <a href="https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f?tpId=295&tqId=2290592&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-12-30
 * Time: 23:01
 */

import java.util.*;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
 }

//思路：根据二叉搜索树的特点和最近公共祖先的特点，我们可以从根节点向下遍历，
//     找到第一个结点的val处于p,q之间的结点，此结点即为最近的公共祖先。
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //因为题目中规定此树节点数大于等于3，且p、q 为不同节点的val,
        //且均存在于给定的二叉搜索树中，因此不需要进行判空处理
        if (root.val < Math.min(p,q)) {
            return lowestCommonAncestor(root.right,p,q);
        }
        if (root.val > Math.max(p,q)) {
            return lowestCommonAncestor(root.left,p,q);
        }
        return root.val;
    }
}